백준 1654 랜선 자르기

백준 1654 랜선 자르기는 전형적인 이분 탐색 문제이다. 문제에서 1~ 2^31-1에 해당하는 랜선길이에 대해 필요한 랜선 개수를 만들 수 있는 최대 랜선 길이를 알아내 출력하는 문제이다. 2^31-1 까지 모든 길이에 대하여 해보면 답은 나오겠지만 이 방법은 너무 느려 시간초과가 뜰 것이다.

그렇다면 여기서 이분 탐색을 이용하여 문제를 풀어나갈 수 있다. left, right 값을 답이 될 수 있는 초기 범위로 잡고 mid에 해당하는 값으로 답을 충족하는지를 보며 left, right 값을 좁혀나가면 답을 좁혀나갈 수 있다. 만약 left가 1이고 right가 400이라면 mid는 200으로 200의 길이로 랜선들을 몇개로 자를 수 있는가로 판단하면 된다.

그리고 리턴된 랜선의 개수가 원하는 값보다 작을 경우 더욱 작은 크기로 쪼개야 하므로 right를 mid-1로 옮긴다. 그 반대의 경우는 left를 mid +1로 옮긴다. 이 과정을 반복하다보면 left == right 인순간이 오게된다. left의 경우 충족하는 값인 경우에도 mid +1로 이동하기 때문에 right를 채택하면 이것이 답이 된다.

#pragma warning(disable:4996)
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<algorithm>
#include<set>
#define INF 987654321
#define ll long long
using namespace std;

int k, n;
vector<int> lansun;

ll retCount(ll len)
{
	ll ret = 0;
	for (int i = 0; i < k; i++)
	{
		ret += lansun[i] / len;
	}

	return ret;
}

int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d %d", &k, &n);

	for (int i = 0; i < k; i++)
	{
		int length;
		scanf("%d", &length);
		lansun.push_back(length);
	}

	ll left = 1;
	ll right = (ll)pow(2, 31) - 1;

	while (left <= right)
	{
		ll mid = (left + right) / 2;
		ll ret = retCount(mid);

		if (ret >= n)
			left = mid + 1;
		else
			right = mid - 1;
	}
	printf("%lld\n", right);
	
}